#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>

///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     struct ListNode *next;
// * };
// */
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
//{
//    struct ListNode* head = NULL;
//    struct ListNode* tail = NULL;
//    //哨兵位的创建
//    head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
//
//    if (list1 == NULL)
//        return list2;
//    if (list2 == NULL)
//        return list1;
//
//    while (list1 && list2)
//    {
//        if (list1->val < list2->val)
//        {
//            tail->next = list1;
//            tail = tail->next;
//            list1 = list1->next;
//        }
//
//        else
//        {
//            tail->next = list2;
//            tail = tail->next;
//            list2 = list2->next;
//        }
//    }
//
//    if (list1)
//        tail->next = list1;
//    if (list2)
//        tail->next = list2;
//
//    //释放哨兵位，返回真正的新链表的头指针
//    struct ListNode* del = head;
//    head = head->next;
//    free(del);
//    return head;
//
//}
//struct ListNode {
//	int val;
//	struct ListNode* next;
//};
//
//struct ListNode2 {
//	int val;
//	struct ListNode2* next;
//};
//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
//{
//	struct ListNode* curA = headA;
//	struct ListNode* curB = headB;
//	int lenA = 1;
//	int lenB = 1;
//	//计算出A链表的长度
//	while (curA->next)
//	{
//		curA = curA->next;
//		lenA++;
//	}
//	//计算出B链表的长度
//	while (curB->next)
//	{
//		curB = curB->next;
//		lenB++;
//	}
//	//如果两个尾节点不一样，则证明不会相交
//	if (curA != curB)
//	{
//		return NULL;
//	}
//	//计算出长度差距
//	int gap = abs(lenA - lenB);
//	//得到正确的长链表（longlist） 和 短链表（shortlist）
//	struct ListNode* longlist = headA;
//	struct ListNode* shortlist = headB;
//	if (lenA < lenB)
//	{
//		longlist = headB;
//		shortlist = headA;
//	}
//	//让长链表（longlist）走到和短链表（shortlist）一样长的时候
//	while (gap)
//	{
//		longlist = longlist->next;
//		gap--;
//	}
//	//两个链表一起往后遍历比较，第一个相同的节点就是相交节点
//	while (1)
//	{
//		longlist = longlist->next;
//		shortlist = shortlist->next;
//		if (longlist == shortlist)
//			return longlist;
//
//	}
//	// //返回相交节点（long和short都行）
//	//  return longlist;
//
//}
//int main()
//{
//	struct ListNode2* n1 = (struct ListNode*)malloc(sizeof(struct ListNode2));
//	struct ListNode2* n2 = (struct ListNode*)malloc(sizeof(struct ListNode2));
//	struct ListNode2* n3 = (struct ListNode2*)malloc(sizeof(struct ListNode2));
//	struct ListNode2* n4 = (struct ListNode2*)malloc(sizeof(struct ListNode2));
//	struct ListNode2* n5 = (struct ListNode2*)malloc(sizeof(struct ListNode2));
//	struct ListNode2* n6 = (struct ListNode2*)malloc(sizeof(struct ListNode2));
//
//
//	n1->val = 5;
//	n2->val = 6;
//	n3->val = 1;
//	n4->val = 8;
//	n5->val = 4;
//	n6->val = 5;
//
//	n1->next = n2;
//	n2->next = n3;
//	n3->next = n4;
//	n4->next = n5;
//	n5->next = n6;
//	n6->next = NULL;
//
//	struct ListNode* m1 = (struct ListNode*)malloc(sizeof(struct ListNode));
//	struct ListNode* m2 = n3;
//	struct ListNode* m3 = n4;
//	struct ListNode* m4 = n5;
//	struct ListNode* m5 = (struct ListNode*)malloc(sizeof(struct ListNode));
//
//	m1->val = 4;
//	m2->val = 1;
//	m3->val = 8;
//	m4->val = 4;
//	m5->val = 5;
//
//	m1->next = m2;
//	m2->next = m3;
//	m3->next = m4;
//	m4->next = m5;
//	m5->next = NULL;
//
//	struct ListNode* p = getIntersectionNode(n1, m1);
//	printf("%p", p);
//
//	return 0;
//}

bool hasCycle(struct ListNode* head)
{
	struct ListNode* slow = head;
	struct ListNode* fast = head;
	while (fast && fast->next)
	{
		fast = fast->next->next;
		slow = slow->next;

		if (slow == fast)
			return true;
	}
	return false;

}